#include <stdio.h>
#include <stdlib.h>
#include "PQ.h"

typedef struct PQnode* link;

struct PQnode{
    Item item;
    link next;
};

static link head;

void PQinit(int maxN){
    head = malloc(sizeof(*head));
    if (head == NULL) {
        // 处理内存分配失败错误，例如打印错误信息并退出
        fprintf(stderr, "Memory allocation failed for dummy head node!\n");
        exit(1);
    }
    head->next = NULL;
}
int PQempty(){
    return head->next == NULL;
}
void PQinsert(Item v){
    link t = malloc(sizeof(*t));
    if (t == NULL) {
        // 处理内存分配失败错误
        fprintf(stderr, "Memory allocation failed for new node!\n");
        exit(1);
    }
    t->item = v;
    link x = NULL;
    for (x = head; x->next != NULL; x = x->next) {
        if (less(x->next->item, v)) {
            break;
        }
    }
    t->next = x->next;
    x->next = t;
}
Item PQdelmax(){
    // 检查队列是否为空 (检查哑头节点的next)
    if (PQempty()) {
         // 处理队列空的情况
         fprintf(stderr, "Priority Queue is empty on PQdelmax!\n");
         exit(1); // 示例：直接退出程序
    }
    link toDelete = head->next;
    Item item = toDelete->item;
    head->next = toDelete->next;

    free(toDelete);
    return item;
}